// 版权所有2009年围棋作者。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

// “抽象”语法表示法。

package ir

import (
	"fmt"
	"go/constant"
	"sort"

	"cmd/compile/internal/base"
	"cmd/compile/internal/types"
	"cmd/internal/src"
)

// 节点是IR节点的抽象接口。
type Node interface {
	// 格式化
	Format(s fmt.State, verb rune)

	// 震源位置。
	Pos() src.XPos
	SetPos(x src.XPos)

	// 用于制作副本。用于复制和复制。
	copy() Node

	doChildren(func(Node) bool) bool
	editChildren(func(Node) Node)

	// 抽象图结构，用于一般遍历。
	Op() Op
	Init() Nodes

	// 仅特定于某些操作的字段。
	Type() *types.Type
	SetType(t *types.Type)
	Name() *Name
	Sym() *types.Sym
	Val() constant.Value
	SetVal(v constant.Value)

	// 用于分析过程的存储。
	Esc() uint16
	SetEsc(x uint16)
	Diag() bool
	SetDiag(x bool)

	// 类型检查值：
	// 0表示节点未进行类型检查
	// 1表示节点已完成类型检查
	// 2表示正在对节点进行类型检查
	// 3表示节点的类型来自types2，但可能需要转换
	Typecheck() uint8
	SetTypecheck(x uint8)
	NonNil() bool
	MarkNonNil()
}

// 第行以字符串形式返回n的位置。如果n已内联，
// 它使用n已内联的最外层位置。
func Line(n Node) string {
	return base.FmtPos(n.Pos())
}

func IsSynthetic(n Node) bool {
	name := n.Sym().Name
	return name[0] == '.' || name[0] == '~'
}

// IsAutoTmp表示如果n是由编译器作为临时文件创建的，
// 基于n名称中.AutoTemp标志的设置。
func IsAutoTmp(n Node) bool {
	if n == nil || n.Op() != ONAME {
		return false
	}
	return n.Name().AutoTemp()
}

// MayBeShared报告是否在AST中的多个位置出现n。
// 在变异这样的节点时必须格外小心。
func MayBeShared(n Node) bool {
	switch n.Op() {
	case ONAME, OLITERAL, ONIL, OTYPE:
		return true
	}
	return false
}

type InitNode interface {
	Node
	PtrInit() *Nodes
	SetInit(x Nodes)
}

func TakeInit(n Node) Nodes {
	init := n.Init()
	if len(init) != 0 {
		n.(InitNode).SetInit(nil)
	}
	return init
}

// go：生成梯边梁-type=Op-trimprefix=O node.go

type Op uint8

// 节点操作。
const (
	OXXX Op = iota

	// 名字
	ONAME // 变量或函数名
	// 未命名的参数或返回值：f（int，string）（int，error）{etc}
	// 还用于尚未解析的限定包标识符。
	ONONAME
	OTYPE    // 类型名
	OPACK    // 进口
	OLITERAL // 字面意义的
	ONIL     // 无

	// 表达
	OADD          // X+Y
	OSUB          // X-Y
	OOR           // X | Y
	OXOR          // X^Y
	OADDSTR       // +{List}（字符串加法，列表元素是字符串）
	OADDR         // &X
	OANDAND       // X&Y
	OAPPEND       // 附加（Args）；在walk之后，X可能包含元素类型描述符
	OBYTES2STR    // 类型（X）（类型为字符串，X为[]字节）
	OBYTES2STRTMP // 类型（X）（类型为字符串，X为[]字节，短暂）
	ORUNES2STR    // 类型（X）（类型是字符串，X是[]符文）
	OSTR2BYTES    // 类型（X）（类型为[]字节，X为字符串）
	OSTR2BYTESTMP // 类型（X）（类型为[]字节，X为字符串，短暂）
	OSTR2RUNES    // 类型（X）（类型是[]符文，X是字符串）
	OSLICE2ARRPTR // 类型（X）（类型是*[N]T，X是a[]T）
	// X=Y或（如果Def=true）X:=Y
	// 如果是Def，那么Init包含X的DCL节点。
	OAS
	// Lhs=Rhs（x，y，z=a，b，c）或（如果Def=true）Lhs:=Rhs
	// 如果是Def，则Init包含Lhs的DCL节点
	OAS2
	OAS2DOTTYPE // Lhs=Rhs（x，ok=I（int））
	OAS2FUNC    // Lhs=Rhs（x，y=f（））
	OAS2MAPR    // Lhs=Rhs（x，ok=m[“foo”]）
	OAS2RECV    // Lhs=Rhs（x，ok=<-c）
	OASOP       // X AsOp=Y（X+=Y）
	OCALL       // X（Args）（函数调用、方法调用或类型转换）

	// OCALLFUNC、OCALLMETH和ocallineter具有相同的结构。
	// 在walk之前，它们是：X（Args），其中Args是所有常规参数。
	// 在walk之后，如果任何参数的计算可能需要临时变量，
	// 该临时变量将被推送到Init，Args将包含更新的
	// 一组参数。KeepAlive是连接到OCALLxxx的所有OVARLIVE节点。
	OCALLFUNC  // X（Args）（函数调用f（Args））
	OCALLMETH  // X（Args）（直接方法调用X.method（Args））
	OCALLINTER // X（Args）（接口方法调用X.method（Args））
	OCALLPART  // X.Sel（方法表达式X.method，未调用）
	OCAP       // 第（X）章
	OCLOSE     // 关闭（X）
	OCLOSURE   // func类型{func.Closure.Body}（func-literal）
	OCOMPLIT   // 类型{List}（复合文字，尚未降低到特定形式）
	OMAPLIT    // 类型{List}（复合文字，类型为map）
	OSTRUCTLIT // 类型{List}（复合文字，类型为struct）
	OARRAYLIT  // 类型{List}（复合文字，类型为数组）
	OSLICELIT  // 类型{List}（复合文字，类型为slice），Len为slice length。
	OPTRLIT    // &X（X是复合文字）
	OCONV      // 类型（X）（类型转换）
	OCONVIFACE // 类型（X）（类型转换，到接口）
	OCONVNOP   // 类型（X）（类型转换，无影响）
	OCOPY      // 副本（X，Y）
	ODCL       // var X（声明X.type类型的X）

	// 在解析期间使用，但不会持续。
	ODCLFUNC  // func f（）或func（r）f（）
	ODCLCONST // 常数pi=3.14
	ODCLTYPE  // 类型Int或类型Int=Int

	ODELETE        // 删除（Args）
	ODOT           // X.Sel（X为结构类型）
	ODOTPTR        // X.Sel（X是指向结构类型的指针）
	ODOTMETH       // X.Sel（X为非接口，Sel为方法名称）
	ODOTINTER      // X.Sel（X为接口，Sel为方法名称）
	OXDOT          // X.Sel（在重写为上述内容之一之前）
	ODOTTYPE       // X.Ntype或X.Type（.Ntype在解析期间，.Type一旦解析）；遍历之后，Itab包含接口类型描述符的地址，Itab.X包含具体类型描述符的地址
	ODOTTYPE2      // X.Ntype或X.Type（.Ntype在解析期间，.Type一旦解析；在OAS2DOTTYPE的rhs上）；遍历之后，Itab包含接口类型描述符的地址
	OEQ            // X==Y
	ONE            // X！=Y
	OLT            // X<Y
	OLE            // X<=Y
	OGE            // X>=Y
	OGT            // X>Y
	ODEREF         // *X
	OINDEX         // X[Index]（数组或切片的索引）
	OINDEXMAP      // X[索引]（地图索引）
	OKEY           // Key:Value（Key:struct/array/map literal中的值）
	OSTRUCTKEY     // 字段：值（键：类型检查后结构文本中的值）
	OLEN           // len（X）
	OMAKE          // make（Args）（在类型检查转换为以下之一之前）
	OMAKECHAN      // make（类型[，Len]）（类型为chan）
	OMAKEMAP       // make（类型[，Len]）（类型为map）
	OMAKESLICE     // make（类型[，Len[，Cap]]）（类型为slice）
	OMAKESLICECOPY // makeslicecopy（Type，Len，Cap）（Type是slice；Len是length，Cap是从slice复制的）
	// OMAKESLICECOPY由订单过程创建，对应于：
	// s=制造（类型，长度）；副本（s，Cap）
	// None
	// 在编译时已知Len==Len（Cap）时，可以在节点上设置Bounded。
	// None
	// 创建此节点是为了使漫游过程可以优化此模式，这将
	// 否则订单通过后很难检测到。
	OMUL         // X*Y
	ODIV         // X/Y
	OMOD         // X%Y
	OLSH         // X<<Y
	ORSH         // X>>Y
	OAND         // X&Y
	OANDNOT      // X&^Y
	ONEW         // 新的（X）；对应于源代码中对new的调用
	ONOT         // !十、
	OBITNOT      // ^X
	OPLUS        // +X
	ONEG         // -X
	OOROR        // X | | Y
	OPANIC       // 恐慌（X）
	OPRINT       // 打印（列表）
	OPRINTN      // println（列表）
	OPAREN       // （十）
	OSEND        // 陈<-价值
	OSLICE       // X[低：高]（X为非类型检查或切片）
	OSLICEARR    // X[低：高]（X是指向数组的指针）
	OSLICESTR    // X[低：高]（X为字符串）
	OSLICE3      // X[低：高：最大]（X为未类型检查或切片）
	OSLICE3ARR   // X[低：高：最大]（X是指向数组的指针）
	OSLICEHEADER // 切片头{Ptr，Len，Cap}（Ptr是不安全的。指针，Len是长度，Cap是容量）
	ORECOVER     // 恢复（）
	ORECV        // <-X
	ORUNESTR     // 类型（X）（类型为字符串，X为符文）
	OSELRECV2    // 类似于OAS2:Lhs=Rhs，其中len（Lhs）=2，len（Rhs）=1，Rhs[0]。Op=ORECV（显示为OCASE的.Var）
	OIOTA        // 极少量
	OREAL        // 实数（X）
	OIMAG        // imag（X）
	OCOMPLEX     // 复合物（X，Y）
	OALIGNOF     // 不安全。校准（X）
	OOFFSETOF    // 不安全。偏移量（X）
	OSIZEOF      // 不安全。Sizeof（X）
	OUNSAFEADD   // 不安全。添加（X，Y）
	OUNSAFESLICE // 不安全。切片（X，Y）
	OMETHEXPR    // 方法表达式

	// 声明
	OBLOCK // {List}（代码块）
	OBREAK // 打破[标签]
	// OCASE:case List:Body（List==nil表示默认值）
	// 对于OTYPESW，List是指定类型（或类型）的OTYPE节点
	// 对于nil），如果指定了类型开关变量，则Rlist是
	// 具有指定类型的类型开关变量版本的ONAME
	// 类型
	OCASE
	OCONTINUE // 继续[标签]
	ODEFER    // 延迟通话
	OFALL     // 失败
	OFOR      // 对于Init；康德；Post{Body}
	// OFORUNTIL与OFOR相似，但试验（Cond）在车身之后进行：
	// 初始化
	// 顶部：{Body}
	// 续：邮政
	// 如果条件{
	// 列表
	// 转到顶端
	// }
	// OfRuntil是通过walk创建的。没有办法用Go代码来写这个。
	OFORUNTIL
	OGOTO   // 转到标签
	OIF     // if Init；Cond{Then}else{else}
	OLABEL  // 标签：
	OGO     // 去打电话
	ORANGE  // 对于键，值=范围X{Body}
	ORETURN // 返回结果
	OSELECT // 选择{Cases}
	OSWITCH // 开关初始化；Expr{Cases}
	// OTYPESW:X:=Y.（类型）（显示为OSWITCH的.Tag）
	// 如果没有类型开关变量，则X为零
	OTYPESW
	OFUNCINST // 泛型函数的实例化

	// 类型
	OTCHAN   // 陈英特
	OTMAP    // 映射[string]int
	OTSTRUCT // 结构{}
	OTINTER  // 接口{}
	// OTFUNC:func（）-Recv是接收方字段，Params是参数字段列表，结果是
	// 结果字段列表。
	OTFUNC
	OTARRAY // [8] int或[…]int
	OTSLICE // []整数

	// 杂项
	// 内联调用的中间表示形式。使用Init（赋值）
	// 对于捕获的变量、参数、retvars和INLMARK op），
	// Body（内联函数的主体）和ReturnVars（
	// 返回值）
	OINLCALL       // 内联调用的中间表示。
	OEFACE         // 接口值为空的itable和数据字。
	OITAB          // 接口值的可编辑字。
	OIDATA         // X中接口值的数据字
	OSPTR          // 片或字符串的基指针。
	OCFUNC         // 对c函数指针的引用（非go func值）
	OCHECKNIL      // 发出代码以确保指针/接口不为零
	OVARDEF        // 变量即将完全初始化
	OVARKILL       // 变量死了
	OVARLIVE       // 变量是活动的
	ORESULT        // 函数调用的结果；Xoffset是堆栈偏移量
	OINLMARK       // 内联正文的开头，带有调用方的文件/行。Xoffset是内联树的索引。
	OLINKSYMOFFSET // 名称内的偏移量

	// 特定于arch的操作码
	OTAILCALL // 对另一个函数的尾部调用
	OGETG     // runtime.getg（）（读取g指针）

	OEND
)

// 节点是指向*节点切片的指针。
// 对于大多数节点中未使用的字段，将使用此字段而不是
// 节省空间的切片。
type Nodes []Node

// 追加将条目追加到节点。
func (n *Nodes) Append(a ...Node) {
	if len(a) == 0 {
		return
	}
	*n = append(*n, a...)
}

// 前置将条目前置到节点。
// 如果传入一个切片，它将拥有它的所有权。
func (n *Nodes) Prepend(a ...Node) {
	if len(a) == 0 {
		return
	}
	*n = append(a, *n...)
}

// 获取clears n，返回其以前的内容。
func (n *Nodes) Take() []Node {
	ret := *n
	*n = nil
	return ret
}

// Copy返回切片内容的副本。
func (n Nodes) Copy() Nodes {
	if n == nil {
		return nil
	}
	c := make(Nodes, len(n))
	copy(c, n)
	return c
}

// NameQueue是一个名为*的FIFO队列。NameQueue的零值为
// 随时可用的空队列。
type NameQueue struct {
	ring       []*Name
	head, tail int
}

// 空报告q是否不包含名称。
func (q *NameQueue) Empty() bool {
	return q.head == q.tail
}

// PushRight将n追加到队列的右侧。
func (q *NameQueue) PushRight(n *Name) {
	if len(q.ring) == 0 {
		q.ring = make([]*Name, 16)
	} else if q.head+len(q.ring) == q.tail {
		// 种植戒指。
		nring := make([]*Name, len(q.ring)*2)
		// 复制旧元素。
		part := q.ring[q.head%len(q.ring):]
		if q.tail-q.head <= len(part) {
			part = part[:q.tail-q.head]
			copy(nring, part)
		} else {
			pos := copy(nring, part)
			copy(nring[pos:], q.ring[:q.tail%len(q.ring)])
		}
		q.ring, q.head, q.tail = nring, 0, q.tail-q.head
	}

	q.ring[q.tail%len(q.ring)] = n
	q.tail++
}

// PopLeft从队列左侧弹出一个名称。如果q是，它会恐慌
// 空的
func (q *NameQueue) PopLeft() *Name {
	if q.Empty() {
		panic("dequeue empty")
	}
	n := q.ring[q.head%len(q.ring)]
	q.head++
	return n
}

// 名称集是一组名称。
type NameSet map[*Name]struct{}

// 已报告s是否包含n。
func (s NameSet) Has(n *Name) bool {
	_, isPresent := s[n]
	return isPresent
}

// 加n加s。
func (s *NameSet) Add(n *Name) {
	if *s == nil {
		*s = make(map[*Name]struct{})
	}
	(*s)[n] = struct{}{}
}

// Sorted返回按less排序的s。
func (s NameSet) Sorted(less func(*Name, *Name) bool) []*Name {
	var res []*Name
	for n := range s {
		res = append(res, n)
	}
	sort.Slice(res, func(i, j int) bool { return less(res[i], res[j]) })
	return res
}

type PragmaFlag int16

const (
	// Func pragmas。
	Nointerface    PragmaFlag = 1 << iota
	Noescape                  // func参数不会转义
	Norace                    // func不能有竞争检测器批注
	Nosplit                   // func不应在单独的堆栈上执行
	Noinline                  // func不应内联
	NoCheckPtr                // checkptr不应检测func
	CgoUnsafeArgs             // 将指向一个参数的指针视为指向所有参数的指针
	UintptrEscapes            // 转换为uintptr转义的指针

	// 仅运行时func pragmas。
	// 有关详细说明，请参见../../../../../runtime/README.md。
	Systemstack        // func必须在系统堆栈上运行
	Nowritebarrier     // 发出编译器错误，而不是写入障碍
	Nowritebarrierrec  // 此被调用方或递归被调用方中的写屏障错误
	Yeswritebarrierrec // 取消此函数中的Nowritebarrierrec并调用

	// 运行时和cgo类型pragmas
	NotInHeap // 此类型的值不能被堆分配

	// 转到命令pragmas
	GoBuildPragma

	RegisterParams // TODO（寄存器参数）在寄存器abi工作后删除

)

func AsNode(n types.Object) Node {
	if n == nil {
		return nil
	}
	return n.(Node)
}

var BlankNode Node

func IsConst(n Node, ct constant.Kind) bool {
	return ConstType(n) == ct
}

// IsNil报告n是否表示通用的非类型化零值“nil”。
func IsNil(n Node) bool {
	// 检查n.Orig，因为常数传播可能会产生类型化的nil常数，
	// Go规范中不存在的。
	return n != nil && Orig(n).Op() == ONIL
}

func IsBlank(n Node) bool {
	if n == nil {
		return false
	}
	return n.Sym().IsBlank()
}

// IsMethod报告n是否为方法。
// n必须是函数或方法。
func IsMethod(n Node) bool {
	return n.Type().Recv() != nil
}

func HasNamedResults(fn *Func) bool {
	typ := fn.Type()
	return typ.NumResults() > 0 && types.OrigSym(typ.Results().Field(0).Sym) != nil
}

// HasUniquePos报告n是否有一个可以
// 用于报告错误消息。
// None
// 它主要用于区分对命名对象的引用，
// 谁的Pos将指向他们的申报位置而不是
// 它们的使用位置。
func HasUniquePos(n Node) bool {
	switch n.Op() {
	case ONAME, OPACK:
		return false
	case OLITERAL, ONIL, OTYPE:
		if n.Sym() != nil {
			return false
		}
	}

	if !n.Pos().IsKnown() {
		if base.Flag.K != 0 {
			base.Warn("setlineno: unknown position (line 0)")
		}
		return false
	}

	return true
}

func SetPos(n Node) src.XPos {
	lno := base.Pos
	if n != nil && HasUniquePos(n) {
		base.Pos = n.Pos()
	}
	return lno
}

// InitExpr的结果必须重新分配给n，例如。
// n、 X=InitExpr（init，n.X）
func InitExpr(init []Node, expr Node) Node {
	if len(init) == 0 {
		return expr
	}

	n, ok := expr.(InitNode)
	if !ok || MayBeShared(n) {
		// 引入OCONVNOP来保存初始列表。
		n = NewConvExpr(base.Pos, OCONVNOP, nil, expr)
		n.SetType(expr.Type())
		n.SetTypecheck(1)
	}

	n.PtrInit().Prepend(init...)
	return n
}

// 写入n影响的外部值是什么？
// 外部值表示包含结构或数组。
func OuterValue(n Node) Node {
	for {
		switch nn := n; nn.Op() {
		case OXDOT:
			base.Fatalf("OXDOT in walk")
		case ODOT:
			nn := nn.(*SelectorExpr)
			n = nn.X
			continue
		case OPAREN:
			nn := nn.(*ParenExpr)
			n = nn.X
			continue
		case OCONVNOP:
			nn := nn.(*ConvExpr)
			n = nn.X
			continue
		case OINDEX:
			nn := nn.(*IndexExpr)
			if nn.X.Type() == nil {
				base.Fatalf("OuterValue needs type for %v", nn.X)
			}
			if nn.X.Type().IsArray() {
				n = nn.X
				continue
			}
		}

		return n
	}
}

const (
	EscUnknown = iota
	EscNone    // 不会转义到堆、结果或参数。
	EscHeap    // 可从堆访问
	EscNever   // 通过建设不会逃逸。
)
